from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        stack = [0] * len(height)
        top = -1
        res = 0
        for i in range(len(height)):
            last = 0
            while top >= 0 and height[stack[top]] <= height[i]:
                res += (i - 1 - stack[top]) * (height[stack[top]] - last)
                last = height[stack[top]]
                top -= 1

            if top >= 0:
                res += (i - 1 - stack[top]) * (height[i] - last)
            stack[top + 1] = i
            top += 1
        return res


print(Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1]))